/*
 * stack.cpp
 *
 *  Created on: Jul 8, 2012
 *      Author: jh238d
 */

#include <stack>
#include <iostream>
using namespace std;

/*To retrieve the current minimum, just return the top element from minimum stack.
Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack too.
When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum stack too.
 *  */
struct StackGetMin{
	stack<int> s;
	stack<int> minStack;

	void push(int data){
		s.push(data);
		if(minStack.empty()||data<=minStack.top()){
			minStack.push(data);
		}
	}

	bool pop(){
		if(s.empty()) return false;
		int data = s.top();
		s.pop();
		if(data==minStack.top()){
			minStack.pop();
		}
		return true;
	}

	bool getMin(int &min){
		if(minStack.empty()) return false;
		else{
			min=minStack.top();
			return true;
		}
	}

};

struct StacksToQueue{
	stack<int> s1;
	stack<int> s2;

	void enqueue(int data){
		s1.push(data);
	}

	bool dequeue(){
		if(!s2.empty()){
			s2.pop();
			return true;
		}
		else if(!s1.empty()) {
			while(!s1.empty()) {
				s2.push(s1.top());
				s1.pop();
			}
			s2.pop();
			return true;
		}else{
			return false;
		}
	}

	int front(){
		if(!s2.empty())
			return s2.top();
		else{
			while(!s1.empty()){
				s2.push(s1.top());
				s1.pop();
			}
			return s2.top();
		}
	}
};
/* Reverse stack
 http://zhedahht.blog.163.com/blog/static/25411174200943182411790/
 */
template<typename T> void reverse_stack(stack<T> &stack){
	if(!stack.empty()){
		T top = stack.top();
		stack.pop();
		reverse_stack(stack);
		add_to_stack_bottom(stack, top);
	}
}

template<typename T> void add_to_stack_bottom(stack<T> &stack, T t){
	if(stack.empty()){
		stack.push(t);
	}else{
		T top=stack.pop();
		stack.pop();
		add_to_stack_bottom(stack, t);
		stack.push(top);
	}
}

